package leetcode.top100.Code39_40组合问题;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 题目1：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 * <p>
 * 说明：解集不能包含重复的子集。
 * <p>
 * 示例:
 * <p>
 * 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
 */
public class Code00_组合数1_无重复数组的子集 {

    public static void main(String[] args) {
        int[] arr = {1,2,3};
        combination1(arr);
        System.out.println(res);
    }

    public static List<List<Integer>> res = new LinkedList<>();

    public static List<List<Integer>> combination1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return res;
        }
        //利用栈只是为了存储当前的结果。
        //如果arr是一个String，那么可以利用String存，不用栈。s+当前(当前要)，或s(当前不要)
        Stack<Integer> stack = new Stack<>();
        process1(arr, 0, stack);
        return res;
    }

    /**
     * 方式1：[1,2,3]输出顺序为：
     * <p>
     * []
     * <p>
     * [1],[1, 2],[1, 2, 3]
     * <p>
     * [1, 3]
     * <p>
     * [2],[2, 3]
     * <p>
     * [3]
     */
    private static void process1(int[] arr, int index, Stack<Integer> stack) {
        //如果要求不能是空，则在这里判断一下，stack是否size为0
        res.add(new LinkedList<>(stack));
        if (index >= arr.length) return;
        for (int i = index; i < arr.length; i++) {
            stack.push(arr[i]);
            process1(arr, i + 1, stack);
            stack.pop();
        }
    }

    /**
     * 方式2：当前位置要或不要。{1,2,3}输出顺序
     * [1, 2, 3]
     * [1, 2]
     * [1, 3]
     * [1]
     * [2, 3]
     * [2]
     * [3]
     * []
     */
    private static void process2(int[] arr, int index, Stack<Integer> stack) {
        if (index == arr.length) {
            //如果要求不能是空，则在这里判断一下，stack是否size为0
            res.add(new LinkedList<>(stack));
            return;
        }
        //当前位置要
        stack.push(arr[index]);
        process2(arr, index + 1, stack);
        stack.pop();
        //当前位置不要
        process2(arr, index + 1, stack);
    }

    /**
     * 如果是字符串或字符数组
     */
    private static void process2(char[] arr, int index, String s) {
        if (index == arr.length) {
            //如果要求不能是空，则在这里判断一下，s是否为空
            //添加结果
            return;
        }
        //当前位置要
        process2(arr, index + 1, s+String.valueOf(arr[index]));
        //当前位置不要
        process2(arr, index + 1, s);
    }
    /**
     * TODO 没有看
     * 我们知道，对于给定一个集合里，所有元素的集合它们应该满足这样一个公式:
     * <p>
     * 假设所有的组合数之和为sum，则有sum = C(n, 0) + C(n, 1) + ...+ C(n, n);
     * <p>
     * 分别对应取集合中的一个元素，两个元素...n个元素。而通过数学公式二项式定义，
     * <p>
     * 这个和是等于2 ** n（2的n次方）。就是说，我们所有取的组合数为一个指数函数。
     * <p>
     * 假设输入是1、2、3。
     * <p>
     * 首先全部的子集为【000】【001】【010】【100】【011】【101】【110】【111】
     * 1表示这一位的数字存在，例如 【010】 表示只含有 2
     * <p>
     * 由此发现子集所代表的二进制数全部小于 1 << 数组.length
     * 第一层循环
     * for (int i = 0; i < (1 << size); i++)
     * <p>
     * 然后根据【i】 的二进制数中 【1】 的位置取得子集
     */
    private static void process4(int[] nums) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        int size = nums.length;
        for (int i = 0; i < (1 << size); i++) {
            List<Integer> ax = new ArrayList<>();
            for (int j = 0; j < size; j++) {
                if ((i & (1 << j)) != 0) {
                    ax.add(nums[j]);
                }
            }
            list.add(ax);
        }
        //return list;
    }


}
